The invention relates to a processing device for executing virtual machine instructions; the processing device comprising: an instruction memory for storing instructions including at least one of the virtual machine instructions; a microcontroller comprising a processor comprising a predetermined microcontroller core for executing native instructions from a predetermined set of microcontroller specific instructions; the native instructions being different from the virtual machine instructions; and a pre-processor comprising: a converter for converting at least one virtual machine instruction, fetched from the instruction memory into at least one native instruction; and feeding means for feeding native instructions to the microcontroller core for execution.
The invention further relates to a pre-processor for use with a microcontroller comprising a processor comprising a predetermined microcontroller core for executing native instructions from a predetermined set of microcontroller specific instructions;
the pre-processor comprising: a converter for converting at least one virtual machine instruction, fetched from an instruction memory, into at least one native instruction; the native instructions being different from the virtual machine instructions; and feeding means for feeding native instructions to the microcontroller core for execution.
Increasingly, source programs are expressed in (compiled to) instructions of a virtual machine instead of native instructions of a microcontroller on which the program is to be executed. A main reason for using a virtual machine is portability of programs between different machines (platforms). A program expressed in the virtual machine instructions of the virtual machine can be executed relatively easily on several concrete machines, using suitable interpreters operating on those machines. At this moment a driving force for using portable programs is Java, where Java programs (referred to as applets) are exchanged via Internet and can be executed on different native machines using processors with different instruction sets. Using a compiler, Java applets are expressed in Java byte codes (JBCs), which form the instructions of the Java Virtual Machine. For embedded applications, a further driving force for using virtual machines is the need for compact code. As the size of software continuously grows, software compression techniques which, due to a certain initial costs, where not attractive before become feasible. One of such techniques is to choose a suitable virtual machine for a specific embedded application, such that the program can be expressed more compactly in the virtual machine instructions than in the native instructions. An example of such a virtual machine is a stack machine, which is known for its compact representation. A specific virtual machine for an embedded application can be defined by first expressing the source program in virtual machine instructions of a chosen virtual machine, such as a stack machine, and additionally, replacing sequences of virtual machine instructions which occur frequently in the compiled code by newly defined additional virtual machine instructions, where, for instance, one new instruction replaces a sequence of four existing instructions.
Conventionally, programs expressed in virtual machine instructions are executed by means of software interpretation. The processor (CPU) executes a special interpreter program, where in a loop the processor fetches a virtual machine instruction, decodes it into a sequence of native instructions of the microcontroller core of the processor and executes each native instruction. This technique is slow and requires an additional interpreter program, which can be relatively large. To improve the execution speed, the so-called Just-In-Time (JIT) compilation technique is used. Just before starting execution of software module expressed in virtual machine instructions, the module is compiled to native code (expressed in native machine instructions). In this way, the module needs to be stored twice in addition to the code for the compiler. The additional storage requirements of software interpretation are not desired for embedded systems. Instead it is preferred to use a hardware interpreter. In itself a hardware interpreter is known in the form of a Prolog pre-processor for Warren""s abstract instruction set. In the paper xe2x80x9cA Prolog pre-processor for Warren""s abstract instruction setxe2x80x9d by B. Knxc3x6dler and W. Rosenstiel, Microprocessing and Microprogramming 18 (1986) pages 71-81, a pre-processor is described for interpreting programs written in the Prolog programming language on a Motorola 68000 processor (MC68000). A compiler is used to translate the Prolog source program into instructions, which have been defined by Mr. Warren and which are generally used for executing Prolog programs. The set of Warren instructions forms a virtual machine designed for executing Prolog programs. The sequence of Warren instructions resulting from the compilation are executed by the MC68000 with the aid of the pre-processor. After power-on, the MC68000 first performs a booting procedure by executing native MC68000 instructions. At the end of the booting procedure, the MC68000 is ready to initiate the execution of a Prolog program. This is started by jumping to a predetermined address range. The pre-processor is a memory-mapped device, which is mapped to this range. When the pre-processor is addressed it reads a Warren instruction (of the translated Prolog program) from its own RAM, adaptively synthesizes a sequence of MC68000 instructions and constants and sends these directly to the CPU for execution. The MC68000 instructions for each Warren instruction are stored in ROM of the pre-processor. In general, the pre-processor translates one Warren instruction into a sequence of MC68000 instructions. The pre-processor contains its own RAM controller and ROM controller, which generate the addresses for the RAM and ROM of the pre-processor. The RAM controller manages the RAM instruction pointer. Each successive read operation of the MC68000 results in the pre-processor sending the next instruction (and optional constants) of the sequence to the CPU. If the sequence has been completed, a next read operation results in the first instruction of the sequence corresponding to the next Warren instruction of the program being send to the CPU. After an interrupt, a repeated read operation of the CPU results in re-sending the last instruction (and optional constants).
It is an object of the invention to provide a processor device of the kind set forth which is suitable for use with a microcontroller which contains more than one instruction at a time.
To achieve the object, the processor is of a type which after the occurrence of a predetermined condition, such as an interrupt, requests re-feeding of up to a predetermined maximum of n native instructions, where n greater than 1; and the feeding means comprises means for in response to the processor requesting re-feeding of a number of native instructions, re-feeding the requested native instructions. The inventor has realised that modern processors can comprise several native instructions at a time, where the execution of the instruction has not yet begun or has not yet been completed, and that in order to increase performance it is desired to exploit the capabilities of the processor of containing more than one instruction. The inventor had the insight that in order to cope with the situation in which the processor discards at least some of the already loaded instructions and at a later stage requests re-feeding of several instructions (e.g. on the occurrence of certain conditions, such as an interrupt), a re-feeding mechanism is required for re-feeding the requested native instructions to the processor.
According to one embodiment, the pre-processor comprises a feeding memory, such as a FIFO, for storing last fed instructions and re-feeding from the feeding memory, providing a simple and effective way of re-feeding the instructions. In view of the fact that in general a virtual machine instruction is converted to a sequence of more than one native instruction, the first native instruction to be re-fed may be any instruction of the sequence. Moreover, the native instruction may correspond to an earlier virtual machine instruction than the current one. Finally, the sequence length may be different for different virtual machine instructions. Using the feeding memory makes it possible to simply re-feed native instructions from the memory instead of retracing virtual machine instructions and the corresponding native instructions.
According to another embodiment, instructions being actively processed in the pipeline of the microcontroller can be re-fed. This makes the pre-processor particularly suitable for use in combination with a RISC-type processor which usually has a pipelined architecture.
According to another embodiment, instructions stored in the instruction cache of the processor can be re-fed. This makes the pre-processor particularly suitable for use in combination with modern processors, such as RISC-type processors, which usually have an instruction cache.
According to another embodiment, instruction stored in the cache or being processed in the pipeline can be re-fed.
According to another embodiment, the feeding memory is capable of storing, in addition to instructions which may need to be re-fed, also instructions which are to be fed for the first time. In this way the pre-processor may in advance generate native instructions before the native instruction is actually requested, avoiding possible delays in feeding a first time requested instruction to the processor. Moreover, it allows the use of only one feeding mechanism which takes care of feeding first time requested instructions and of re-feeding instructions.
One aspect of the invention is directed to a simple and effective way for unifying first time feeding and re-feeding. The instructions which have already been fed and the instruction(s) still to be fed are stored successively in the feeding memory, such as a FIFO. Logically the pre-processor maintains a pointer indicating a memory location in the feeding memory containing the instruction expected to be requested next (i.e. the first instruction which has not yet been requested before). In practice, this memory location may always be at a fixed position of the feeding memory, so that no separate pointer needs to be maintained. The pre-processor comprises a counter which indicates an address of the native instruction expected to be requested next by the processor for first time feeding. Normally, each time a native instruction has been fed for the first time, the counter is incremented. The processor indicates (using an instruction pointer) an address of the instruction required next by the processor. This may be a request for a first time feeding or a re-feeding of an instruction. The pre-processor compares the requested address to the address stored in the counter. Based on the offset, the instruction is located in the feeding memory. For instance, the counter may store the address of the instruction expected to be requested next, being one higher than the address of the instruction fed last. If indeed the processor requests this new instruction, the offset is zero. If the logical pointer points to the location of the new instruction, the instruction stored at this location is fed to the processor. If the processor requests re-feeding of the previous instruction, the offset may be one or minus one (counted in units of an instruction, which may be 4 counted in units of bytes for a 32-bit instruction). By subtracting (or respectively adding) the offset from the pointer the requested instruction is located. It will also be appreciated that the counter and the logical pointer do not need to store the exact address/location of the instruction expected to be requested next. For instance, the logical pointer may also indicate the last fed instruction.
Another aspect of the invention is directed to an alternative arrangement where no additional feeding memory is required. Instead the pre-processor stores state information which enable recreating the instructions requested by the processor for refeeding. As an example, instead of storing fed instructions in a feeding memory, also pointers indicating instructions or information used to initially create the instructions may be stored in a memory.
In one embodiment, part of the state is stored in the instruction pointer of the microcontroller, potentially reducing the costs of the pre-processor.
In another embodiment, the pre-processor comprises for at least one virtual machine instruction a corresponding translation table for translating the virtual machine instruction into a sequence of native instructions. The translation table may, for instance, be stored in ROM. The least significant part of the instruction pointer of the processor is used to indicate which of the native instructions in the table is required (i.e. the least-significant part of the instruction pointer acts as a translation table offset indicator). During normal operation, the processor automatically increments the instruction pointer. Advantageously, the pre-processor does not need to store an own counter and increment this counter for indicating the native instruction expected to be read next. If the processor requests a re-feeding, the processor will automatically set the instruction pointer to a previous value. In this way also re-feeding can be taken care of automatically.
The measure defined in dependent claim 11 provides an effective way for determining, in addition to the translation table offset, also the translation table in which the requested native instruction is located. A predetermined further part of the instruction pointer comprises a virtual machine instruction pointer indicating a virtual machine instruction in the instruction memory. This virtual machine instruction pointer can be seen as a virtual machine program counter, which needs to be incremented each time a new virtual machine instruction is required. The pre-processor fetches the virtual machine instruction indicated by the virtual machine instruction pointer from the instruction memory and based on the fetched virtual machine instruction locates the translation table. The least significant part of the instruction pointer of the processor is then used as an offset in the translation table. Whenever a sequence of native instructions relating to one virtual machine instruction has been completed, the virtual machine instruction pointer can be set to indicate the next virtual machine instruction, for instance, by using as a last native instruction in the sequence an explicit jump which sets the virtual machine instruction pointer to the desired value and resets the translation offset part of the instruction pointer or using one or more NOP (no operation) instructions so that eventually an overflow of the translation offset part results in the processor incrementing the virtual machine instruction pointer. It will be appreciated that it is not required that each request from the processor for an instruction results in fetching a virtual machine instruction from the instruction memory. Advantageously, the pre-processor comprises a cache for storing already fetched or expected to be fetched virtual machine instructions from the instruction memory.
Advantageously, as an alternative to a full native instruction the translation table contains a native instruction skeleton for at least native instructions with variable parts. The skeleton comprises predetermined fixed parts of the native instruction, such as the operation code, whereas variable elements of the instruction, such as certain operands, are loaded adaptively, for instance from parameters of the corresponding virtual machine instruction.
Another aspect of the invention provides an alternative for the use of the virtual machine instruction pointer. In this embodiment the translation table is divided into several sub-tables, at least one of the sub-tables comprising a sequence of native instructions or native instruction skeletons. A sub-table may but does not need to correspond to a complete sequence of native instructions corresponding to one virtual instruction. In practice it may be preferred to choose a sub-table size of only 4 or 8 native instructions, which may be less than the maximum sequence of native instructions for a virtual machine instruction. The translation table offset indicator indicates an offset in one of the sub-tables. A predetermined further part of the instruction pointer comprises a sub-table indicator. The pre-processor uses the value of the sub-table indicator to locate the actually involved sub-table. Preferably, in normal operation the sub-table indicator is incremented by one unit each time a native instruction is fetched from a next sub-table (regardless of the sub-table being related to the same or different virtual machine instructions). The pre-processor may store pointers to the related sub-table(s) for the last used sub-table indicators. Particularly for relatively small sub-tables, a sequence of native instructions relating to one virtual machine instruction may be complemented by NOP instructions in order to ensure that the sequence ends on a sub-table boundary (eliminating the use of jump operations to correct the value of the sub-table indicator part of the instruction pointer). Most processors can execute a NOP operation significantly faster than a jump operation.
The measure defined in the dependent claim 13 ensures that no deadlock situation can occur wherein the processor has requested an instruction and blocks the bus until the instruction has been supplied, whereas the pre-processor first needs to obtain a (virtual machine) instruction from the instruction memory via the same bus before it can supply the native instruction.
These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments shown in the drawings.